home *** CD-ROM | disk | FTP | other *** search
/ Loadstar 14 / 014.d81 / useful lemma < prev    next >
Text File  |  2022-08-26  |  963b  |  64 lines
  1.  
  2.            A USEFUL LEMMA
  3.  
  4.  
  5.  
  6.   In the MATHEMATICAL REFLECTIONS
  7.  
  8. column of issue 13 of LOADSTAR we
  9.  
  10. included a nice little program which
  11.  
  12. computes the GCD of two integers by
  13.  
  14. repeated use of the Euclidean
  15.  
  16. Algorithm.
  17.  
  18.   We could have gone on to say that:
  19.  
  20.  
  21. LEMMA: If (A,B) represents the GCD of
  22.  
  23. the two integers A and B, then there
  24.  
  25. always exist integers C and D such
  26.  
  27. that
  28.  
  29.           AC + BD = (A,B).
  30.  
  31. This result will not be proved here,
  32.  
  33. but it can be found in any text on
  34.  
  35. elementary number theory. If you FEEL
  36.  
  37. like doing it yourself, use the method
  38.  
  39. we used in issue 13 to generate the
  40.  
  41. GCD of A and B by repeated use of the
  42.  
  43. Euclidean Algorithm. Substitution from
  44.  
  45. one line to the next provides you
  46.  
  47. with the desired integers C and D.
  48.  
  49.   As an example, (7,5)=1, that is the
  50.  
  51. greatest common divisor of 7 and 5 is
  52.  
  53. 1. Thus there must exist integers C
  54.  
  55. and D such that
  56.  
  57.            7C + 5D = 1.
  58.  
  59. Try C=3 and D=-4.
  60.  
  61. --------------------------------------
  62.  
  63.  
  64.